Probe points are frequently captured by global positioning systems (“GPS”), navigation systems or the like. Each probe point is associated with a location, such as may be expressed in terms of latitude and longitude. Some probe points are also associated with a heading and a speed at which the GPS system or the navigation system was moving at the time at which the probe point was captured.
In some instances, such as within a region for which a map consisting of a plurality of road segments has been created, the probe points may be matched to the map in order to identify the location along a road segment at which the probe point was captured. Map matching may be performed in real time, such as by navigation systems in order to identify the location of the probe point relative to the road segments represented by the map. For example, navigation systems mounted within a vehicle may perform real time map matching in order to depict the relative position of a probe point upon a map, thereby illustrating the current location of the vehicle. Map matching for real time applications may only utilize the path of probe points up to the most recent probe point since those are the only probe points that are known. Alternatively, map matching may rely upon post-processing, such as in instances in which the probe points captured by a plurality of GPS systems or navigation systems are matched to the road segments represented by a map for traffic estimation or other purposes. The accuracy of the map matching provided by post-processing may be improved relative to the map matching for real time applications since probe points captured subsequent in time to the probe point currently being processed are also known and may be referenced during the post-processing.
A variety of probe-centric map matching techniques have been developed. These map matching techniques include map matching techniques that utilize geometric analysis including point-to-point analysis, point-to-curve analysis and trajectory techniques. Other map matching techniques utilize a topological analysis of the road network to improve accuracy and performance. Some map matching techniques utilize probabilistic map-matching algorithms. The probabilistic map-matching algorithms attempt to identify the most probable road segment in some confidence region about a respective probe point. Additionally or alternatively, probabilistic map-matching algorithms may attempt to identify the most probable path in addition to the most probable road segment. The probabilistic map-matching algorithms may include, for example, Viterbi and hidden Markov model techniques. Further, map-matching techniques may include other types of map-matching algorithms including those that utilize Kalman and extended Kalman based techniques and those that utilize particle filters.
Whether performed in real time or as a post-processing technique, map matching has been a probe-centric process in which each probe point is analyzed to identify the closest road segment and the projection of the probe point onto the closest road segment. In order to identify the closest road segment, a separate spatial search is generally conducted for each probe point; even in instances in which a probe point is spaced a substantial distance from any road segment. Thus, the number of spatial searches to be conducted is generally proportional to the number of probe points.
Spatial searches are computationally expensive. For example, probe-centric map matching techniques for large probe data sets, such as millions of probe points, can incur substantial execution time and costs since the number of spatial searches is proportional to the number of probe points. Thus, map matching and, in particular, the spatial searches for each of the probe points may become a limiting factor at least for real time applications.
In an effort to perform map matching more quickly and efficiently, a map-centric map matching technique has been developed as described by U.S. patent application Ser. No. 14/752,159 entitled Map-Centric Map Matching Method and Apparatus and filed Jun. 26, 2015, the entire contents of which are incorporated herein by reference. The map-centric map matching technique may, in many instances, conduct fewer spatial searches since the spatial searches are no longer proportional in number to the number of probe points and are, instead, based upon the length of the road segments of the map to which the probe points are to be matched. As a result, the map-centric map matching technique may map match the probe points in a more efficient manner.
However, map-centric map matching techniques may be unable to map match probe points to respective road segments with a desired level of confidence at ambiguous locations within a road network. As shown in FIG. 1, ambiguous locations at which probe points cannot be map matched to respective road segments with a sufficient level of confidence by map-centric map matching techniques may include crossing roads, both crossing roads at grade and crossing roads not at grade, for which probe points have the same or similar headings as shown at 10 in FIG. 1, adjacent or parallel roads for which the probe points have the same or similar probe headings as shown at 12 in FIG. 1, and ramps or bifurcations in which a roadway splits or merges as shown at 14 in FIG. 1. At these ambiguous locations along the road network, the probe points may be incorrectly map matched to the wrong road segment. Even if map matched to the correct road segment, the confidence value associated with the map matched probe point may be lower than is desirable. Although the results for the map matching of probe points at ambiguous locations may be improved by the utilization of probabilistic map matching, the probe points may still not be map matched to the correct road segments with sufficient accuracy and/or with a desired level of confidence.